package com.leetcode.LC_MED;

public class LC376 {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][2];
        // 0 i 作为波峰的最大长度
        // 1 i 作为波谷的最大长度
        dp[0][0] = 1;
        dp[0][1] = 1;

        for (int i = 1; i < len; i++) {
            //i 自己可以成为波峰或者波谷
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) {
                    // i是波谷
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]) {
                    // i是波峰
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }
            }
        }

        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }

    public int wiggleMaxLength_2(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > nums[i]) {
                down = up + 1;
            }
            if (nums[i - 1] < nums[i]) {
                up = down + 1;
            }
        }
        return Math.max(down, up);
    }
}
